//===--- GlobalLoopARCSequenceDataflow.cpp --------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "arc-sequence-opts"

#include "polarphp/pil/optimizer/internal/arc/GlobalLoopARCSequenceDataflow.h"
#include "polarphp/pil/optimizer/internal/arc/ARCRegionState.h"
#include "polarphp/pil/optimizer/analysis/ARCAnalysis.h"
#include "polarphp/pil/optimizer/analysis/RCIdentityAnalysis.h"
#include "polarphp/pil/lang/PILInstruction.h"
#include "polarphp/pil/lang/PILFunction.h"
#include "polarphp/pil/lang/PILSuccessor.h"
#include "llvm/Support/Debug.h"

using namespace polar;

//===----------------------------------------------------------------------===//
//                                  Utility
//===----------------------------------------------------------------------===//

/// Returns true if it is defined to perform a bottom up from \p Succ to \p
/// Pred.
///
/// This is interesting because in such cases, we must pessimistically assume
/// that we are merging in the empty set from Succ into Pred or vis-a-versa.
static bool isDefinedMerge(const LoopRegion *Succ, const LoopRegion *Pred) {
   // If the predecessor region is an unknown control flow edge tail, the
   // dataflow that enters into the region bottom up is undefined in our model.
   if (Pred->isUnknownControlFlowEdgeTail())
      return false;

   // If the successor region is an unknown control flow edge head, the dataflow
   // that leaves the region bottom up is considered to be undefined in our
   // model.
   if (Succ->isUnknownControlFlowEdgeHead())
      return false;

   // Otherwise it is defined to perform the merge.
   return true;
}

//===----------------------------------------------------------------------===//
//                             Top Down Dataflow
//===----------------------------------------------------------------------===//

void LoopARCSequenceDataflowEvaluator::mergePredecessors(
   const LoopRegion *Region, ARCRegionState &State) {
   bool HasAtLeastOnePred = false;

   for (unsigned PredID : Region->getPreds()) {
      auto *PredRegion = LRFI->getRegion(PredID);
      auto &PredState = getARCState(PredRegion);

      LLVM_DEBUG(llvm::dbgs() << "    Merging Pred: " << PredID << "\n");

      // If this merge is undefined due to unknown control flow, assume that the
      // empty set is flowing into this block so clear all state and exit early.
      if (!isDefinedMerge(Region, PredRegion)) {
         State.clear();
         break;
      }

      if (HasAtLeastOnePred) {
         State.mergePredTopDown(PredState);
         continue;
      }

      State.initPredTopDown(PredState);
      HasAtLeastOnePred = true;
   }
}

bool LoopARCSequenceDataflowEvaluator::processLoopTopDown(const LoopRegion *R) {
   assert(!R->isBlock() && "Expecting to process a non-block region");
   LLVM_DEBUG(llvm::dbgs() << "Processing Loop#: " << R->getID() << "\n");

   bool NestingDetected = false;

   // For each RegionID in our reverse post order...
   for (unsigned SubregionIndex : R->getSubregions()) {
      auto *Subregion = LRFI->getRegion(SubregionIndex);
      auto &SubregionData = getARCState(Subregion);

      // This will always succeed since we have an entry for each BB in our RPOT.
      LLVM_DEBUG(llvm::dbgs() << "Processing Subregion#: " << SubregionIndex
                              << "\n");

      // Ignore blocks that allow leaks.
      if (SubregionData.allowsLeaks()) {
         LLVM_DEBUG(llvm::dbgs() << "Skipping leaking BB.\n");
         continue;
      }

      LLVM_DEBUG(llvm::dbgs() << "Merging Predecessors for subregion!\n");
      mergePredecessors(Subregion, SubregionData);

      // Then perform the dataflow.
      NestingDetected |= SubregionData.processTopDown(
         AA, RCFI, LRFI, DecToIncStateMap, RegionStateInfo, SetFactory);
   }

   return NestingDetected;
}

//===----------------------------------------------------------------------===//
//                             Bottom Up Dataflow
//===----------------------------------------------------------------------===//

void LoopARCSequenceDataflowEvaluator::mergeSuccessors(const LoopRegion *Region,
                                                       ARCRegionState &State) {

   bool HasAtLeastOneSucc = false;

   for (unsigned SuccID : Region->getLocalSuccs()) {
      auto *SuccRegion = LRFI->getRegion(SuccID);
      auto &SuccState = getARCState(SuccRegion);

      LLVM_DEBUG(llvm::dbgs() << "    Merging Local Succ: " << SuccID << "\n");

      // If this merge is undefined due to unknown control flow, assume that the
      // empty set is flowing into this block so clear all state and exit early.
      if (!isDefinedMerge(SuccRegion, Region)) {
         State.clear();
         break;
      }

      // If this successor allows for leaks, skip it. This can only happen at the
      // function level scope. Otherwise, the block with the unreachable
      // terminator will be a non-local successor.
      //
      // At some point we will expand this to check for regions that are post
      // dominated by unreachables.
      if (SuccState.allowsLeaks())
         continue;

      if (HasAtLeastOneSucc) {
         State.mergeSuccBottomUp(SuccState);
         continue;
      }

      State.initSuccBottomUp(SuccState);
      HasAtLeastOneSucc = true;
   }

   for (unsigned SuccID : Region->getNonLocalSuccs()) {
      auto *SuccRegion = LRFI->getRegionForNonLocalSuccessor(Region, SuccID);
      auto &SuccState = getARCState(SuccRegion);

      LLVM_DEBUG(llvm::dbgs() << "    Merging Non Local Succs: " << SuccID
                              << "\n");

      // Check if this block is post dominated by ARC unreachable
      // blocks. Otherwise we clear all state.
      //
      // TODO: We just check the block itself for now.
      if (SuccState.allowsLeaks()) {
         LLVM_DEBUG(llvm::dbgs() << "        Allows leaks skipping\n");
         continue;
      }

      // Otherwise, we treat it as unknown control flow.
      LLVM_DEBUG(llvm::dbgs() << "        Clearing state b/c of early exit\n");
      State.clear();
      break;
   }
}

/// Analyze a single BB for refcount inc/dec instructions.
///
/// If anything was found it will be added to DecToIncStateMap.
///
/// NestingDetected will be set to indicate that the block needs to be
/// reanalyzed if code motion occurs.
///
/// An epilogue release is a release that post dominates all other uses of a
/// pointer in a function that implies that the pointer is alive up to that
/// point. We "freeze" (i.e. do not attempt to remove or move) such releases if
/// FreezeOwnedArgEpilogueReleases is set. This is useful since in certain cases
/// due to dataflow issues, we cannot properly propagate the last use
/// information. Instead we run an extra iteration of the ARC optimizer with
/// this enabled in a side table so the information gets propagated everywhere in
/// the CFG.
bool LoopARCSequenceDataflowEvaluator::processLoopBottomUp(
   const LoopRegion *R, bool FreezeOwnedArgEpilogueReleases) {

   bool NestingDetected = false;

   // For each BB in our post order...
   auto Start = R->subregion_begin(), End = R->subregion_end();
   if (Start == End)
      return false;

   --End;
   while (Start != End) {
      unsigned SubregionIndex = *End;
      auto *Subregion = LRFI->getRegion(SubregionIndex);
      auto &SubregionData = getARCState(Subregion);

      // This will always succeed since we have an entry for each BB in our post
      // order.
      LLVM_DEBUG(llvm::dbgs() << "Processing Subregion#: " << SubregionIndex
                              << "\n");

      LLVM_DEBUG(llvm::dbgs() << "Merging Successors!\n");
      mergeSuccessors(Subregion, SubregionData);

      // Then perform the region optimization.
      NestingDetected |= SubregionData.processBottomUp(
         AA, RCFI, EAFI, LRFI, FreezeOwnedArgEpilogueReleases, IncToDecStateMap,
         RegionStateInfo, SetFactory);
      --End;
   }

   {
      unsigned SubregionIndex = *End;
      auto *Subregion = LRFI->getRegion(SubregionIndex);
      auto &SubregionData = getARCState(Subregion);

      // This will always succeed since we have an entry for each BB in our post
      // order.
      LLVM_DEBUG(llvm::dbgs() << "Processing Subregion#: " << SubregionIndex
                              << "\n");

      LLVM_DEBUG(llvm::dbgs() << "Merging Successors!\n");
      mergeSuccessors(Subregion, SubregionData);

      // Then perform the region optimization.
      NestingDetected |= SubregionData.processBottomUp(
         AA, RCFI, EAFI, LRFI, FreezeOwnedArgEpilogueReleases, IncToDecStateMap,
         RegionStateInfo, SetFactory);
   }

   return NestingDetected;
}

//===----------------------------------------------------------------------===//
//                 Top Level ARC Sequence Dataflow Evaluator
//===----------------------------------------------------------------------===//

LoopARCSequenceDataflowEvaluator::LoopARCSequenceDataflowEvaluator(
   PILFunction &F, AliasAnalysis *AA, LoopRegionFunctionInfo *LRFI,
   PILLoopInfo *SLI, RCIdentityFunctionInfo *RCFI,
   EpilogueARCFunctionInfo *EAFI,
   ProgramTerminationFunctionInfo *PTFI,
   BlotMapVector<PILInstruction *, TopDownRefCountState> &DecToIncStateMap,
   BlotMapVector<PILInstruction *, BottomUpRefCountState> &IncToDecStateMap)
   : Allocator(), SetFactory(Allocator), F(F), AA(AA), LRFI(LRFI), SLI(SLI),
     RCFI(RCFI), EAFI(EAFI), DecToIncStateMap(DecToIncStateMap),
     IncToDecStateMap(IncToDecStateMap) {
   for (auto *R : LRFI->getRegions()) {
      bool AllowsLeaks = false;
      if (R->isBlock())
         AllowsLeaks |= PTFI->isProgramTerminatingBlock(R->getBlock());
      RegionStateInfo[R] = new (Allocator) ARCRegionState(R, AllowsLeaks);
   }
}

LoopARCSequenceDataflowEvaluator::~LoopARCSequenceDataflowEvaluator() {
   for (auto P : RegionStateInfo) {
      P.second->~ARCRegionState();
   }
}

bool LoopARCSequenceDataflowEvaluator::runOnLoop(
   const LoopRegion *R, bool FreezeOwnedArgEpilogueReleases,
   bool RecomputePostDomReleases) {
   bool NestingDetected = processLoopBottomUp(R, FreezeOwnedArgEpilogueReleases);
   NestingDetected |= processLoopTopDown(R);
   return NestingDetected;
}

void LoopARCSequenceDataflowEvaluator::summarizeLoop(
   const LoopRegion *R) {
   RegionStateInfo[R]->summarize(LRFI, RegionStateInfo);
}

void LoopARCSequenceDataflowEvaluator::summarizeSubregionBlocks(
   const LoopRegion *R) {
   for (unsigned SubregionID : R->getSubregions()) {
      auto *Subregion = LRFI->getRegion(SubregionID);
      if (!Subregion->isBlock())
         continue;
      RegionStateInfo[Subregion]->summarizeBlock(Subregion->getBlock());
   }
}

void LoopARCSequenceDataflowEvaluator::clearLoopState(const LoopRegion *R) {
   for (unsigned SubregionID : R->getSubregions())
      getARCState(LRFI->getRegion(SubregionID)).clear();
}

void LoopARCSequenceDataflowEvaluator::addInterestingInst(PILInstruction *I) {
   auto *Region = LRFI->getRegion(I->getParent());
   RegionStateInfo[Region]->addInterestingInst(I);
}

void LoopARCSequenceDataflowEvaluator::removeInterestingInst(
   PILInstruction *I) {
   auto *Region = LRFI->getRegion(I->getParent());
   RegionStateInfo[Region]->removeInterestingInst(I);
}
